#include <iostream>
#include <string>
#include <functional>
using namespace std;
class Tree {
	struct Node {
		char val;
		Node* lchild = nullptr;
		Node* rchild = nullptr;
		Node() : val{}, lchild{ nullptr }, rchild{ nullptr } {}
		Node(char _val) : val{ _val }, lchild{ nullptr }, rchild{ nullptr } {}
	};

	Node* root = nullptr;
public:
	Tree(string s) {
		function<void(Node*&, int&, const string&)> dfs = [&](Node*& node, int& i, const string& s) {
			if (i >= s.size() or s[i] == '#') return;
			node = new Node(s[i]);
			dfs(node->lchild, ++i, s);
			dfs(node->rchild, ++i, s);
		};
		int index = 0;
		dfs(root, index, s);
	}

	~Tree() {
		function<void(Node*)> dfs = [&](Node* node) {
			if (node->lchild) dfs(node->lchild);
			if (node->rchild) dfs(node->rchild);
			delete node;
		};
		if (root) dfs(root);
	}

	void prePrint() {
		function<void(Node*)> dfs = [&](Node* node) {
			if (not node) return;
			cout << node->val << " ";
			dfs(node->lchild);
			dfs(node->rchild);
		};
		dfs(root);
		cout << endl;
	}

	void midPrint() {
		function<void(Node*)> dfs = [&](Node* node) {
			if (not node) return;
			dfs(node->lchild);
			cout << node->val << " ";
			dfs(node->rchild);
		};
		dfs(root);
		cout << endl;
	}

	void sufPrint() {
		function<void(Node*)> dfs = [&](Node* node) {
			if (not node) return;
			dfs(node->lchild);
			dfs(node->rchild);
			cout << node->val << " ";
		};
		dfs(root);
		cout << endl;
	}
};


int main() {
	//string s = "AB##C##";
	//Tree tree(s);
	//tree.prePrint();
	//tree.midPrint();
	//tree.sufPrint();

	string s = "ABC##D##EF##G##";
	Tree tree(s);
	tree.prePrint();
	tree.midPrint();
	tree.sufPrint();
}